\section{Preliminary Definitions}  
\label{sec:definitions}
In this section, we present some important definitions.

\textbf{Data.} We use an RDF-based graph-structured model to accommodate different kinds of structured data. 
\begin{definition}[Data Graph] The data is conceived as a set of graphs $\mathbf{G}$. Let $U$ denote the set of Uniform Resource Identifiers (URIs) and $L$ the set of literals, every $G \in\mathbf{G}$ is a set of triples of the form $\langle s, p, o \rangle$, where  $s \in U$ (called subject), $p \in U$ (predicate) and  $o \in U \cup L$ (object). 
%form the vocabulary $V = U \cup L$. 
%
%\[
%Pred(s, G)=\{p | \langle s,p,o \rangle \in G\}
%\]
\end{definition}

Every (set of) instance  is represented as a set of triples.  

\begin{definition}[Instance Representation] It is  defined as:  $IR(G, S) = \{\langle s, p, o \rangle$ $| \langle s, p, o \rangle \in G, s \in S \}$, where  $G$ is a graph and $S$ a set of instances in $G$. It yields a set of triples in which $s \in S$ appears as the subject. We denote the set of objects associated with an instance $s$ over the predicate $p$ in $G$ as $O(s,p,G)$, with $O(s,p, G)=\{o | \langle s,p,o \rangle \in G\}$.
\end{definition} 

The representation of a single instance $s$ is $IR(G,$ $\{s\})$. 
%We will use the terms instance and instance representation interchangeably from now on. 
%For simplicity, we use in this work the outgoing edges $(s, p, o)$ of a resource $s$ to form its representation $IR(G, \{s\})$.
% However, other types of representations that may include incoming edges, as well as more complex structures in the data (e.g. paths instead of edges), are applicable. 

\textbf{Features.} Now, we define the features of a set of instances $X$.
%First, we introduce the concept of features of a set of instances $X$, and then, we define a class, an important concept used throughout this paper. 

\begin{definition}[Features] Let $G$ be a dataset and $X$ be a set of instances in $G$. The features of $X$ are: 

\begin{itemize}
%\setlength{\itemsep}{-4pt}
	\item $A(X) = \{p | (s, p, o) \in IR(G, X) \land s \in X\}$,
    \item $D(X) = \{o | (s, p, o) \in IR(G, X) \land s \in X \land o \in L \}$,
	\item $O(X) = \{o | (s, p, o) \in IR(G, X) \land s \in X \land o \in U \}$, 
	\item $T(X) = \{(p,o) | (s, p, o) \in IR(G, X) \land s \in X \}$,
	\item  $F(X) = A(X) \cup D(X)\cup O(X)\cup T(X)$.
%	\vspace{-4pt}
\end{itemize}
\end{definition}  

Note $A(X)$ is the set of predicates, $D(X)$ the set of literals, $O(X)$ the set of URIs, and $T(X)$ is the set of predicate-object pairs in the representation of $X$. 

Considering  $X=$\{\verb+db:Belmont_California+\}, its features are: $A(x)=$\{\verb+rdfs:label+, \verb+db:country+\}, $D(x)=$ \{ 'Belmont'\}, $O(x)=$\{\verb+db:Usa+\}, and $T(x)=$\{(\verb+rdfs:+ \verb+label+, 'Belmont'), (\verb+db:country+, \verb+db:Usa+)\}. 
Hence, $F(X)=$\{ \verb+rdfs:label+, \verb+db:country+, 'Belmont', \verb+db:Usa+\, (\verb+rdfs:+ \verb+label+, 'Belmont'), (\verb+db:country+, \verb+db:Usa+)\}. 

Note that $A(x)$ captures the predicates, which are schema-level features instances of a class typically have in common. However, we do not only use $A(x)$ but the whole union set $F(X)$, which comprises both schema- and data-level features. This is due to our special notion of class and the way we compute it: instances belong to a class when they share some features - no matter schema or data-level features.
% In this way, both types of features are leveraged for inferring the class instances belong to.  

\textbf{Class}. We define a class as follows:
 

\begin{definition}[Class] Let $G$ be a dataset and $X$ a set of instances in $G$, $X$ is a class if  $\forall x \in X: F(\{x\}) \cap F(X - \{x\}) \neq \emptyset$.
\end{definition}

Intuitively, a class is set of instances, where every instance in this set has at least one feature in common  with any other instance in this set. \par
%definition considers any feature equally relevant.
%we cannot assume that  instances (in the heterogeneous setting) will share any particular feature (e.g., $A(\bullet)$). 
%For example, in a heterogeneous dataset, two distinct instances in the same class may have different predicates with the same semantics. One  may have the predicate \verb+locatedIn+ with value "UK" and another  the predicate \verb+placedIn+ with value "UK". In this case, $A(\bullet)$ features does not define their syntax similarity (our approach only consider the syntactical similarities), but still we can consider they are similar based only on the value "UK".  

%Especially in heterogeneous data, this definition is important because  instances of a class may not necessarily share the same predicates but at least their values. 


%This class definition takes into account that a set of instances in the heterogeneous setting may not share a fixed schema, where all instances have at least the same attributes (e.g.\ latitude, longitude and population), and may have missing attributes (e.g.\ two countries can be represented differently, one with the attribute latitude and the other without it.). Notice, that this definition does not require all instances in the class to share a common feature, e.g.\ if at least two instances in $X$ share only the features $O(X)=\{"UK"\}$, then we consider that $X$ defines the class of instances that has a value "UK". Especially in heterogeneous data, this class definition is required  because  instances of a class may not necessarily share the same predicates but at least their values. 


%In addition, one purpose of class-based matching is to find a set of instances (among all candidates) that form a concise class, i.e.\ where the similarity   (w.r.t. to $F(\bullet)$)  of its constituent instances is maximized.   Also, class-based matching tries to maximize the number of instances in the class that matches to the source instances. In this process,  only the candidate instances are considered.

%Notice that this class definition is not limited to a\ $T(\cdot)$ type of features. For example, as well as \ $K=$\{(\verb+db:type+, \verb+db:Country+)\} defines the set of instances of the type country (i.e., countries),   $K=$\{\verb+geo:long+\}  defines set of instances with a longitude attribute (e.g., locations), and $K=$ \{"Mayor"\} defines the set of instances with literal value "Mayor" (e.g., cities or cities' mayor).  

%Typically, only predicate-object pairs (i.e.\ $T(\cdot)$ type of features) are used for direct matching. For our problem of class-based matching, we use these features not only to represent instances but also classes. Hence, not only instance-specific but also class-related features such as $A(X)$, are useful.  For example, the predicate \verb+geo:long+ is a good descriptor for the class location, while \verb+corp:revenue+ is a good feature for representing the class company.  
 
